Computer networks are tools by which data may be transferred from one computer system to another. This data is usually transmitted in the form of data packets, which have embedded in them the network address of both the source and destination systems. By deconstructing the network address of the destination, devices known as routers are used to send each packet closer to its final destination.
In the network known as the Internet, these network addresses are known as Internet Protocol (IP) Addresses. IP addresses, in their human-readable representation (also known as dot notation), consist of four decimal values from 0 up to and including 255 separated by periods. In their machine representation, IP addresses are a 32-bit word.
Other protocols are typically embedded in the IP protocol. One of these is TCP, which uses a port number to distinguish services and individual streams of data. Port numbers may be any number from 1 up to 65535, with the first 1023 being assigned specific tasks. Web browsing, for instance, uses the HTTP protocol on port 80 while email transfers use the SMTP protocol on port 25.
Although the primary purpose of routers is to facilitate the transfer of data on the internet, they are also used to control access. Each physical connection from the router is known as an interface, and routers typically contain tables of rules which specify through which interface, if any, a particular data packet should be sent. One kind of table is known as an Access Control List or an Action Control List, both hereinafter refereed to as an ACL, which contains Access Control Entries (ACEs).
Access control lists provide a mechanism to match either the source address, the destination address, and/or the protocol of an incoming packet, with a directive describing what should be done with a matching packet. Though ACLs are non-homogenous across platforms, they always have an option to allow or deny a matching packet. Some router systems may also have the option to limit the rate of matching packets, or to forward the packets to an alternate interface. ACLs are evaluated in-order, so that the first matching ACE determines the destiny of the packet. The comparison of ACE's within ACL's is well known in terms of whether the comparison is done by software, hardware, or a hybrid system, therefore a discussion of basic ACE comparison modalities is not included herein, other than noting that the basic system requirements for interaction include a programmable processor for executing a software program to implement the instant method, a memory for storing and manipulating ACL's and their constituent ACE's and a user interface, preferably including a screen for the user to view the ACL or individual ACE.
The matching of IP addresses is done through a netmask, which looks much like an address in its dotted notation. In its underlying machine representation, however, a netmask consists of a 32-bit word that typically has only its most significant bits set. The function of the netmask is to define a range of IP addresses that are considered to be a common network.
In medium to large organizations, ACLs may become extremely large, and the difficulty of maintaining the lists increases geometrically as the number of entries grows. Large ACLs also take more time to process, slowing down the data transfer rate across the router. The size of the ACL, therefore, should be kept as small as possible. The following is an example of an excerpt form typical ACL which in fact contains many more ACEs. Certain ACEs have been adjusted for illustration purposes:
Entry 1:denyip 88.0.0.07.255.255.255Entry 2:denyip 96.0.0.031.255.255.255Entry 3:denyip 169.254.0.00.0.255.255Entry 4:denyip 172.0.0.00.255.255.255Entry 5:denyip 172.16.0.00.0.255.255Entry 6:denyip 192.0.2.00.0.0.255Entry 7:permitip 192.0.0.00.255.255.255Entry 8:denyip 192.168.0.00.0.255.255Entry 9:denyip 197.0.0.00.255.255.255Entry 10:denyip 198.18.0.00.1.255.255Entry 11:denyip 201.0.0.00.255.255.255Entry 12:denyip 222.0.0.01.255.255.255Entry 13:denyip 224.0.0.031.255.255.255Entry 14:denyall others.
Managing large access control lists brings many challenges. Matching access control entries takes time, so a poorly structured ACL may severely impact network performance. As well, for every ACE added to the list, the likelihood of conflicts between entries within the same list increase. These conflicts may take three forms.
The first kind of conflict is called a shadowed ACE, which means that the matching rules of the ACE are a subset of the matching pattern of a previous ACE and their directives are different. An ACE may become shadowed, for instance as in the ACL above, looking at the ACEs referring to a designation starting with 192. If an ACE accepts packets with a destination starting with 192 and a later ACE denies packets with a destination starting with 192.168. In this case, the latter ACE will never be reached. Shadowing is the most severe kind of conflict, as it may cause inadvertent security holes (in the case of a mistaken access), or a loss of service (in the case of a mistaken denial). In this regard note that with respect to the last two ACEs directed to the destination starting with 192, the denial of 192.168.0.0 will be ineffective.
The second kind of conflict is called forward redundancy. A forward redundancy is created when the matching rules of an ACE are a subset of the matching pattern of a previous ACE and their directives are the same. In this case, the latter ACE is rendered useless by the former ACE, as the pattern will never match while processing a packet. An example of forward redundancy in the ACL segment above is illustrated by the ACE which denies a packet with an address starting with 172 and a later ACE which denies a packet with a destination of 172.16, the latter ACE is useless.
The third kind of conflict is called backward redundancy. ACEs are backward redundant when the matching rules of the ACE are a subset of the matching pattern of a subsequent ACE, the directives are identical, and there is no pattern between them which has a different directive and is a subset of the ACE. The later ACE is essentially making the former ACE useless. As an example, if an ACE accepts packets starting with 192.0.2.0 and later the ACE accepts packets starting with 192, then the first entry is redundant.
Of these three, backward redundancy is the least harmful, as the more precise rule could have been inserted intentionally as an optimization procedure.
Managing large access control lists is an onerous and error-prone task. The order of ACEs in the ACL become more important and their relationship becomes more complicated. The likelihood of conflicts within an ACL increases geometrically with size. Conflicts within an ACL may cause security breaches, loss of service, decreased data throughput and increased latency.
Another specific problem is caused by lengthy ACL's. Each network packet is processed through the ACL until a match is made. The comparison between the packet and the ACL entry requires a measurable amount of time for each packet and ACE. The amount of time to process the packet through the ACL is the sum of each of the ACE comparisons. If the average time to process a packet through and ACL is greater than the average time between packets entering the router, then the router cannot process all of the packets effectively. The router must then choose to drop the unfiltered packets (obviously this causes network problems or outages) or the router may choose to pass the unfiltered packets which may have a worse effect than dropping them as it gives the network clients no protection at all.